package org.example.myleet.p695;

public class Solution {

    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    private static final int WATER = 0;
    private static final int LAND = 1;

    public int maxAreaOfIsland(int[][] grid) {
        int nr = grid.length, nc = grid[0].length;
        boolean[][] visited = new boolean[nr][nc];
        int size = 0;
        int[][] pointStack = new int[nr * nc][2];
        int maxArea = 0;
        for (int i = 0; i < nr; ++i) {
            for (int j = 0; j < nc; ++j) {
                if (visited[i][j]) {
                    continue;
                }
                if (grid[i][j] == LAND) {
                    pointStack[size++] = new int[]{i, j};
                }
                int area = 0;
                while (size > 0) {
                    int len = size;
                    for (int idx = 0; idx < len; ++idx) {
                        //pop
                        int[] p = pointStack[--size];
                        //将土地置为水，防止重复访问此块土地
                        grid[p[0]][p[1]] = WATER;
                        ++area;
                        visited[p[0]][p[1]] = true;
                        for (int[] DIRECTION : DIRECTIONS) {
                            int[] np = new int[]{p[0] + DIRECTION[0], p[1] + DIRECTION[1]};
                            if (0 <= np[0] && np[0] < nr && 0 <= np[1] && np[1] < nc) {
                                if ((!visited[np[0]][np[1]]) && grid[np[0]][np[1]] == LAND) {
                                    visited[np[0]][np[1]] = true;
                                    pointStack[size++] = np;
                                }
                            }
                        }
                    }
                }
                maxArea = Math.max(maxArea, area);
            }
        }
        return maxArea;
    }
}
